◀ Prev · Parts · Full · Next ▶

• the exploitation of limited independence in the random variables used by the algorithm, such as the pairwise independence used in universal hashingcite-ref-24[24]

• the use of expander graphs (or dispersers in general) to amplify a limited amount of initial randomness (this last approach is also referred to as generating pseudorandom bits from a random source, and leads to the related topic of pseudorandomness)

• changing the randomized algorithm to use a hash function as a source of randomness for the algorithm's tasks, and then derandomizing the algorithm by brute-forcing all possible parameters (seeds) of the hash function. This technique is usually used to exhaustively search a sample space and making the algorithm deterministic (e.g. randomized graph algorithms)

◀ Prev · Parts · Full · Next ▶